#include "RegEx.h"

namespace FiniteAutomata
{
	void Parser::Eval()
	{
		Operator op = operatorStack.top();
		operatorStack.pop();

		switch (op)
		{
		case Operator::Star:
			Star();
			break;
		case Operator::Union:
			Union();
			break;
		case  Operator::Concat:
			Concat();
			break;
		}
	}

	void Parser::Concat()
	{
		// TODO: Divide the canvas horizontally
		TransitionTable table2 = transitionTableStack.top();
		transitionTableStack.pop();
		// TODO: Render table2
		TransitionTable& table1 = transitionTableStack.top();
		// TODO: Render table1
		// TODO: Merge final state of table1 and initial state of table2

		// Add transitions of table2's starting state to table1's final state
		Transitions& transitions = table2[0]->transitions;
		for (Transitions::const_iterator i = transitions.cbegin();
			i != transitions.cend();
			i++)
		{
			table1[table1.size() - 1]->AddTransition(*i);
		}

		// Add table2's states to table1.
		table1.insert(table1.end(), table2.begin() + 1, table2.end());
	}

	void Parser::Star()
	{
		if (transitionTableStack.empty())
		{
			ParsingException exception;
			exception.message = "Unexpected *, missing operand";
			throw exception;
		}

		TransitionTable& table = transitionTableStack.top();
		// TODO: Render table

		shared_ptr<State> start = CreateNewState();
		shared_ptr<State> end = CreateNewState();
		// TODO: Render start and end

		AddTransition(start, 0, end);
		AddTransition(start, 0, table[0]);
		AddTransition(table[table.size() - 1], 0, end);
		AddTransition(table[table.size() - 1], 0, table[0]);

		table.push_back(end);
		table.push_front(start);
	}

	void Parser::Union()
	{
		if (transitionTableStack.empty())
		{
			ParsingException exception;
			exception.message = "Unexpected |, missing both operands";
		}

		// TODO: Split the canvas vertically
		TransitionTable table2 = transitionTableStack.top();
		transitionTableStack.pop();
		// TODO: Render table2
		
		if (transitionTableStack.empty())
		{
			ParsingException exception;
			exception.message = "Unexpected |, missing left operand";
		}

		TransitionTable& table1 = transitionTableStack.top();
		// TODO: Render table1

		shared_ptr<State> start = CreateNewState();
		shared_ptr<State> end = CreateNewState();
		// TODO: Render start and end

		AddTransition(start, 0, table1[0]);
		AddTransition(start, 0, table2[0]);
		AddTransition(table1[table1.size() - 1], 0, end);
		AddTransition(table2[table2.size() - 1], 0, end);

		table1.push_front(start);
		table1.insert(table1.end(), table2.begin(), table2.end());
		table1.push_back(end);
	}

	void Parser::FromSingleChar(char ch)
	{
		// TODO: Clean canvas

		shared_ptr<State> state1 = CreateNewState();
		shared_ptr<State> state2 = CreateNewState();
		// TODO: Render these states
		AddTransition(state1, ch, state2);

		TransitionTable table;
		table.push_back(state1);
		table.push_back(state2);

		transitionTableStack.push(table);
	}
	
	void Parser::AddTransition(shared_ptr<State> s1, char ch, shared_ptr<State> s2)
	{
		s1->AddTransition(ch, s2);
		// TODO: add an edge from s1 to s2
	}

	NondeterministicFiniteAutomaton Parser::CreateNFA(string s)
	{
		// Thompson's construction. Reference: algorithm 3.3, Aho, Sethi, and Ullman
		while (!transitionTableStack.empty())
		{
			transitionTableStack.pop();
		}

		while (!operatorStack.empty())
		{
			operatorStack.pop();
		}

		for (unsigned int i = 0; i < s.length(); i ++)
		{
			char c = s[i];
			// TODO: animate reading of c

			if (!IsOperator(c))
			{
				FromSingleChar(c);
			}
			else
			{
				Operator op = ToOperator(c);
				if (op == Operator::LeftParen)
				{
					operatorStack.push(op);
				}
				else if (op == Operator::RightParen)
				{
					// Evaluate everyting in paranthesis
					while (!operatorStack.empty() && operatorStack.top() != Operator::LeftParen)
					{
						Eval();
					}

					if (operatorStack.empty())
					{
						ParsingException exception;
						exception.message = "Unmatched ')'";
						throw exception;
					}

					// Remove left paranthesis after the evaluation
					operatorStack.pop();
				}
				else
				{
					while (!operatorStack.empty() && operatorStack.top() <= op)
					{
						Eval();
					}
					operatorStack.push(op);
				}
			}

			// Push a Concat on the operator stack if there is a contact operation coming up.
			// This is needed because concat operation is implicit, unlike other operators.
			// Before doing that, evaluate the stack till we see a lower precedence operator.
			
			if (i != s.length() - 1)
			{
				char next = s[i + 1];
				if ((!IsOperator(c) || c == ')' || c == '*') && (!IsOperator(next) || next == '('))
				{
					while (!operatorStack.empty() && operatorStack.top() <= Operator::Concat)
					{
						Eval();
					}
					operatorStack.push(Operator::Concat);
				}
			}
		}

		while (!operatorStack.empty())
		{
			Eval();
		}

		NondeterministicFiniteAutomaton result;
		result.transitionTable = transitionTableStack.top();
		transitionTableStack.pop();
		return result;
	}

	/*
	DeterministicFiniteAutomaton Parser::ConvertNFAtoDFA(NondeterministicFiniteAutomaton nfa)
	{
	// Convert an NFA to a DFA. The algorithm is known as the subset construction.
	// Reference: Fig 3.25, Aho, Sethi, and Ullman
	DeterministicFiniteAutomaton result;

	// Mapping a DFA state to corresponding NFA states (the subset).
	map<shared_ptr<State>, set<shared_ptr<State>>> stateToClosureMapping;
	vector<shared_ptr<State>> unmarkedStates;

	// Initially, e-closure(s0) is the only state in Dstates and it is unmarked.
	set<shared_ptr<State>> nfaStartStateSet;
	nfaStartStateSet.insert(nfa.transitionTable[0]);

	shared_ptr<State> s = CreateNewState();
	stateToClosureMapping.insert(make_pair(s, EpsilonClosure(nfaStartStateSet)));
	result.transitionTable.push_back(s);
	unmarkedStates.push_back(s);

	// while there is an unmarked state T in Dstates do
	while (!unmarkedStates.empty())
	{
	// mark T
	shared_ptr<State> t = unmarkedStates[unmarkedStates.size() - 1];
	unmarkedStates.pop_back();

	// collect the set of inputs of T;
	set<char> inputSet;
	set<shared_ptr<State>> nfaStates = stateToClosureMapping[t];
	for (set<shared_ptr<State>>::const_iterator i = nfaStates.cbegin(); i != nfaStates.cend(); i++)
	{
	for (Transitions::const_iterator j = (*i)->transitions.cbegin();
	j != (*i)->transitions.cend();
	j = (*i)->transitions.upper_bound(j->first))
	{
	if (j->first != 0)
	{
	inputSet.insert(j->first);
	}
	}
	}

	// for each input signal a do
	for (set<char>::const_iterator i = inputSet.cbegin(); i != inputSet.cend(); i++)
	{
	set<shared_ptr<State>> closure = EpsilonClosure(Move(*i, stateToClosureMapping[t]));

	shared_ptr<State> u(nullptr);
	for (TransitionTable::const_iterator j = result.transitionTable.cbegin(); j != result.transitionTable.cend(); j++)
	{
	if (stateToClosureMapping[*j] == closure)
	{
	u = *j;
	break;
	}
	}

	if (u == nullptr)
	{
	u = CreateNewState();
	stateToClosureMapping.insert(make_pair(u, closure));
	unmarkedStates.push_back(u);
	result.transitionTable.push_back(u);
	}

	t->AddTransition(*i, u);
	}
	}
	return result;
	}

	set<shared_ptr<State>> Parser::EpsilonClosure(set<shared_ptr<State>> states)
	{
	// Reference: Fig 3.25, Aho, Sethi, and Ullman
	set<shared_ptr<State>> result;
	result = states;

	stack<shared_ptr<State>> unprocessedStates;
	for_each(states.cbegin(), states.cend(),
	[&unprocessedStates](shared_ptr<State> s)
	{
	unprocessedStates.push(s);
	});

	while (!unprocessedStates.empty())
	{
	// Remove the first state from the unprocessed states
	shared_ptr<State> t = unprocessedStates.top();
	unprocessedStates.pop();

	// Get all epsilon transitions for this state
	vector<shared_ptr<State>> epsilonStates;
	for (Transitions::const_iterator i = t->transitions.lower_bound(0);
	i != t->transitions.upper_bound(0);
	i++)
	{
	epsilonStates.push_back(i->second);
	}

	// For each state u reachable from t via an e-transition, add it to the result
	// as well as the set of unprocessed states
	for (vector<shared_ptr<State>>::const_iterator i = epsilonStates.cbegin();
	i != epsilonStates.cend();
	++i)
	{
	if (result.find(*i) == result.end())
	{
	result.insert(*i);
	unprocessedStates.push(*i);
	}
	}
	}

	return result;
	}

	set<shared_ptr<State>> Parser::Move(char ch, set<shared_ptr<State>> states)
	{
	set<shared_ptr<State>> result;

	for (set<shared_ptr<State>>::const_iterator i = states.cbegin(); i != states.cend(); i++)
	{
	for (Transitions::const_iterator j = (*i)->transitions.lower_bound(ch);
	j != (*i)->transitions.upper_bound(ch);
	j++)
	{
	result.insert(j->second);
	}
	}
	return result;
	}
	*/
}